package cn.datastruct.EightTree;

/**
 * 未完
 * 双旋转为补充完
 * 节点高度需要修改一下
 * 使用旋转的位置需要怎斟酌
 * 2021/3/17 22：00
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10, 12, 8, 9, 7, 6};
        int length = arr.length;
        AVLTree AVL = new AVLTree();
        for (int i = 0; i < length; i++) {
            AVL.add(new TreeNode(arr[i]));
            AVL.rightRotate();
        }
        System.out.println(AVL.height());
        System.out.println(AVL.rightHeight());
        System.out.println(AVL.leftHeight());
    }
}

class AVLTree extends BinarySortTree {//继承二叉排序树的method

    //调整二叉平衡树的位置

    /**
     * 思路：
     * 左旋转：
     * 1.创建一个新的节点，并把当前节点的值赋给新节点
     * 2.新节点的左子树指向当前root节点的左子树
     * 3.新节点的右子树指向当前root节点的右子树的左节点
     * 4.当前root节点的右子树节点的值赋给root节点
     * 5.当前root节点的左子树节点指向新节点
     * 6.当前root的右子树指向原先右子树的右节点
     */
    public void leftRotate(){
        this.leftRotate(root);
    }

    public void leftRotate(TreeNode node) {

        //高度大于1就调整
        if (rightHeight(node) - leftHeight(node) > 1) {
            //创建一个新的节点，并把当前节点的值赋给新节点
            TreeNode temp = new TreeNode(node.val);
            //新节点的左子树指向当前root节点的左子树
            temp.left = node.left;
            //新节点的右子树指向当前root节点的右子树的左节点
            temp.right = node.right.left;
            //当前root节点的右子树节点的值赋给root节点
            node.val = node.right.val;
            //当前root节点的左子树节点指向新节点
            node.left = temp;
            //当前root的右子树指向原先右子树的右节点
            node.right = node.right.right;
        }
    }
    /**
     * 思路：
     * 右旋转：
     * 1.创建一个新的节点，并把当前节点的值赋给新节点
     * 2.新节点的右子树指向当前root节点的右子树
     * 3.新节点的左子树指向当前root节点的左子树的右节点
     * 4.当前root节点的左子树节点的值赋给root节点
     * 5.当前root节点的右子树节点指向新节点
     * 6.当前root的左子树指向原先左子树的左节点
     */

    public void rightRotate(){
        this.rightRotate(super.root);
    }
    public void rightRotate(TreeNode node){
        if (leftHeight(node) - rightHeight(node) > 1) {
            TreeNode temp = new TreeNode(node.val);
            temp.right = node.right;
            temp.left = node.left.right;
            node.val = node.left.val;
            node.right = temp;
            node.left = node.left.left;
        }
    }

    //左子树高度
    public int leftHeight() {
        return this.leftHeight(root);
    }

    public int leftHeight(TreeNode node) {
        if (node.left == null) {
            return 0;
        } else {
            return this.height(node.left);
        }
    }

    //右子树高度
    public int rightHeight() {
        return this.rightHeight(super.root);
    }

    public int rightHeight(TreeNode node) {
        if (node.right == null) {
            return 0;
        } else {
            return this.height(node.right);
        }
    }

    //求出高度
    public int height() {
        return height(root);
    }

    public int height(TreeNode node) {
        return Math.max(node.left == null ? 0 : this.height(node.left), node.right == null ? 0 : this.height(node.right)) + 1;
    }
}
